package com.sicheng.algorithm.array.sorted;

import com.sicheng.algorithm.common.Sort;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/1/22 18:48
 */
public class HeapSorted {

    public static void main(String[] args) {
        HeapSorted heapSorted = new HeapSorted();
        int[] arr = {2, 88, 7, 1, 3, 10, 9, 2, 9};
        heapSorted.heapSorted(arr);
        System.out.println(Arrays.toString(arr));
    }

    public void heapSorted(int[] arr) {
        if (arr == null || arr.length <= 1)
            return;
        int size = arr.length;
        heapify(arr, size);//大顶堆化
        while (size-- > 0) {
            Sort.swap(arr, 0, size);
            siftDown(arr, size, 0, arr[0]);
        }

    }

    public void heapify(int[] arr, int size) {
        int i = (size >>> 1) - 1;
        for (; i >= 0; i--) {
            siftDown(arr, size, i, arr[i]);
        }
    }

    /**
     * 简单模仿优先队列的源码, 实现堆排序
     *
     * @param arr  逻辑堆
     * @param size 逻辑容量
     * @param k    当前指针
     * @param e    下沉元素
     */
    private void siftDown(int[] arr, int size, int k, int e) {
        int half = size >>> 1;//移位运算===(size / 2)
        while (k < half) {
            int child = (k << 1) + 1;
            if (child + 1 < size && arr[child + 1] > arr[child])//找到左右孩子中优先级最高的索引
                child += 1;
            if (arr[child] <= e)//孩子优先级不够高，下浮失败
                break;
            arr[k] = arr[child];
            k = child;
        }
        arr[k] = e;
    }
}
